package 三傻排序;

/**
 * @author 冷加宝
 * @version 1.0
 */
public class Select_Bubble_Insert {

    // 主方法用于测试
    public static void main(String[] args) {
        int N = 20;
        int V = 10;
        int testTimes = 5000;
        System.out.println("+++开始测试+++");
        for(int i = 0; i < testTimes; i++){
            int n = (int)(Math.random() * N);
            int[] arr = randomArray(n, V);
            int[] arr1 = copyArray(arr);
            int[] arr2 = copyArray(arr);
            int[] arr3 = copyArray(arr);
            selectSort(arr1);
            bubbleSort(arr2);
            insertSort(arr3);
            if(!sameArray(arr1, arr2) || !sameArray(arr1, arr3)){
                System.out.println("出错了。。。");
            }
        }
        System.out.println("----测试结束---");
    }

    public static int[] randomArray(int n, int v){
        int[] arr = new int[n];
        for(int i = 0; i < arr.length; i++){
            arr[i] = (int)(Math.random() * v) + 1;
        }
        return arr;
    }

    public static int[] copyArray(int[] arr){
        int n = arr.length;
        int[] copyArr = new int[n];
        for(int i = 0; i < n; i++){
            copyArr[i] = arr[i];
        }
        return copyArr;
    }

    public static boolean sameArray(int[] arr1, int[] arr2){
        for(int i = 0; i < arr1.length; i++){
            if(arr1[i] != arr2[i]){
                return false;
            }
        }
        return true;
    }

    public static void swap(int i, int j, int[] arr){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    //选择排序
    public static  void selectSort(int[] arr){
        if(arr == null || arr.length < 2){
            return;
        }
        //0~n-1, 1~n-1,.. 每次找到最小值的位置minIndex与i位置上的值交换
        for(int i = 0; i < arr.length-1; i++){
            int minIndex = i;//i~n-1 位置上，最小值的位置
            //0  1   2  ...   n-1
            //  min    min    min 找最小值的位置
            for(int j = i+1; j < arr.length; j++){
                if(arr[j] < arr[minIndex]){
                    minIndex = j;
                }
            }
            swap(i, minIndex, arr);
        }
    }

    //冒泡排序
    public static void bubbleSort(int[] arr){
        if(arr == null || arr.length < 2){
            return;
        }
        //0~n-1, 0~n-2,...每次把最大的数往右冒，搞定最右侧
        for(int end = arr.length-1; end > 0; end--){
            for(int j = 0;j < end;j++){
                if(arr[j] > arr[j+1]){
                    swap(j, j+1, arr);
                }
            }
        }
    }

    //冒泡排序
    public static void bubbleSort2(int[] arr){
        if(arr == null || arr.length < 2){
            return;
        }
        int end = arr.length-1, i = 0;
        while(end > 0){
            if(arr[i] > arr[i+1]){
                swap(i, i+1, arr);
            }
            if(i == end-1){
                i = 0;
                end--;
            }else{
                i++;
            }
        }
    }

    //插入排序
    public static  void insertSort(int[] arr){
        if(arr == null || arr.length < 2){
            return;
        }
        for(int i = 1; i < arr.length; i++){
            for(int j = i-1; j >= 0 && arr[j] > arr[j+1]; j--){
                swap(j, j+1, arr);
            }
        }
    }

}
